package com.gsy.lcs;

import java.util.Arrays;

public class LCSWithMemory {
    public static void main(String[] args) {
        System.out.println(findLCS4("abcdefghij","fghijabcde"));
        System.out.println(findLCSubstring("abcdefghij","fghijabcde"));
    }
    //时间复杂度度回溯过程仅为m+n,箭头是需要记录的
    public static String findLCS4(String s1,String s2) {
        char arr1[] = s1.toCharArray();
        char arr2[] = s2.toCharArray();
        int dp[][] = new int[s1.length()+1][s2.length()+1];
        int memory[][] = new int[s1.length()+1][s2.length()+1];
        Arrays.fill(memory[0],-1);
        for (int i = 1; i <= s1.length() ; i++) {
            memory[i][0] = -1;
            for (int j = 1; j <= s2.length() ; j++) {
                if (arr1[i-1] == arr2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    memory[i][j] = 3;
                }else {
                    if (dp[i][j-1] > dp[i-1][j]) {
                        dp[i][j] = dp[i][j-1];
                        memory[i][j] = 1;
                    }else {
                        dp[i][j] = dp[i-1][j];
                        memory[i][j] = 2;
                    }
                }
            }
        }
        int i = s1.length();
        int j = s2.length();
        char re[] = new char[dp[s1.length()][s2.length()]];
//        System.out.println(re.length);
        int index = re.length-1;
        while (true) {
            if (memory[i][j] == 3){
                re[index--] = arr1[i-1];
                i--;
                j--;
            }else if (memory[i][j] == 2){
                i--;
            }else if (memory[i][j] == 1){
                j--;
            }else {
                break;
            }
        }
        return new String(re);
    }

    public static String findLCSubstring(String s1,String s2) {
        int dp[][] = new int[s1.length()+1][s2.length()+1];
        int max = -1;
        int maxEnd = -1;
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length() ; j++) {
                if (s1.charAt(i-1) ==  s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if (max < dp[i][j]) {
                        maxEnd = i;
                        max = dp[i][j];
                    }
                }else {
                    dp[i][j] = 0;
                }
            }
        }
        return (s1.substring(maxEnd - max ,maxEnd));
    }
}
